package A1动态规划;

public class LC_188买卖股票的最佳时机IV {
    public static void main(String[] args){
        int[] prices={2,4,1};
        int k=2;
        System.out.println(maxProfit(k,prices));
    }
    public static int maxProfit(int k, int[] prices) {
        int[][] dp=new int[prices.length][2*k+1];
        for(int j=1;j<2*k;j+=2)
            dp[0][j]=-prices[0];
        for(int j=0;j<2*k;j+=2)
            dp[0][j]=0;
        for(int i=1;i<prices.length;i++){
            for(int j=0;j<2*k;j+=2){
                dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            }
        }
        return dp[prices.length-1][2*k];
    }
}
